/**
 * LeetCode 70. 爬楼梯
 */
public class Solution_70 {
    /**
     * 方法三：斐波那契数列通项公式
     * <p>
     * f(n) = [ ((1 + sqrt5) / 2) ^ n - ((1 - sqrt5) / 2) ^ n ] / sqrt5
     */
    public int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double fib_n = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
        return (int) (fib_n / sqrt5);
    }

    /**
     * 方法二：动态规划-空间优化
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int climbStairs2(int n) {
        int p = 0, q = 0, ans = 1;
        for (int i = 1; i <= n; i++) {
            p = q;
            q = ans;
            ans = p + q;
        }
        return ans;
    }

    /**
     * 方法一：动态规划
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public int climbStairs1(int n) {
        // dp[i] 表示到达第 i 级台阶的方法
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
